package com.gxc.tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 单词搜索 II

 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
 *
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，
 * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
 */
public class FindWords {

    public static void main(String[] args) {
        findWords(new char[][]{
                        {'o','a','a','n'},
                        {'e','t','a','e'},
                        {'i','h','k','r'},
                        {'i','f','l','v'}
                }
                , new String[]{"oath","pea","eat","rain"});
        System.out.println("-------------");
    }

    public static List<String> findWords(char[][] board, String[] words) {
        MyTrie trie = new MyTrie();
        for (String word : words) {
            trie.insert(word);
        }

        int m = board.length;
        int n = board[0].length;
        boolean[][] visit = new boolean[m][n];

        int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};

        Set<String> res = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = true;
                dfs(i, j, board, dirs, visit, trie, res);
                visit[i][j] = false;
            }
        }
        return  new ArrayList<String>(res);
    }

    private static void dfs(int x, int y, char[][] board, int[][]  dirs, boolean[][] visit,  MyTrie trie, Set<String> res) {
        char c = board[x][y];
        int index = c - 'a';

        MyTrie cur = trie.trie[index];
        if (cur == null) return;
        if (!"".equals(cur.word)) {
            res.add(cur.word);
        }

        for (int i = 0; i < dirs.length; i++) {
            int[] dir = dirs[i];
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX>=0 && newX<board.length && newY>=0 && newY<board[0].length && !visit[newX][newY]) {
                visit[newX][newY] = true;
                dfs(newX, newY, board, dirs, visit, cur, res);
                visit[newX][newY] = false;
            }
        }
    }



}

class MyTrie {
    MyTrie[] trie;
    String word;

    public MyTrie() {
        this.word = "";
        this.trie = new MyTrie[26];
    }

    public void insert(String word) {
        MyTrie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if (node.trie[index] == null) {
                node.trie[index] = new MyTrie();
            }
            node = node.trie[index];
        }
        node.word = word;
    }
}
